1. Field of the Invention
The present invention relates generally to road design, and in particular, to a method, apparatus, and article of manufacture for defining a vertical road profile design with engineering constraints.
2. Description of the Related Art
(Note: This application references a number of different publications as indicated throughout the specification by reference numbers enclosed in brackets, e.g., [x]. A list of these different publications ordered according to these reference numbers can be found below in the section entitled “References.” Each of these publications is incorporated by reference herein.)
In road design, computer aided design (CAD) users try to draw road profiles that follow the existing ground as close as possible. This reduces the overall earthwork costs (cut and fill). However, in most cases, there are design constraints that need to be imposed on the profile, such as (1) maximum positive and negative grades, (2) minimal required grade for drainage (no flat sections allowed), (3) maximum grade change, and (4) the profiles need to go through some fixed points (intersections with other roads, etc.).
Often times, an initial design that follows the ground closely does not respect all of the constraints described above (e.g., infeasible with respect to one or more constraints). Prior art methods attempt to impose such constraints on an existing profile using linear programming (LP). An example of such a method is given in the publication “A note on: Spline technique for modeling roadway profile to minimize earthwork cost”, by Valentin Koch and Yves Lucet, Volume 6 (2), pages 393-400, Journal of Industrial and Management Optimization (Published March 2010). Some of the constraints (e.g., constraints 1, 3, and 4) can be incorporated as linear constraints into an LP. However, constraint (2) is not linear and can therefore not be added to an LP. A possible way to solve the problem with constraint (2) would be with the help of a mixed-integer linear program (MIP). There are several disadvantages for using a MIP. First, a MIP can be very slow and can take up to hours to solve large problem instances. Second, a MIP requires sophisticated solver software (often commercially licensed) to solve the problem.
In an LP approach, one uses linear equations and a complex algorithm such as the simplex algorithm or interior-point methods, to solve the problem. In a MIP approach, one adds integer variables to linear equations. In a MIP, the same algorithms as in an LP are used, but in a procedure called branch-and-bound, where an LP is solved thousands or millions of times. This makes the MIP approach very slow.
In view of the above, what is needed is a fast and accurate method for determining and modifying a spline to comply with a set of design constraints. In particular, it is desirable to use a method, apparatus, and system that can modify a civil engineering spline while satisfying a set of constraints that are both linear and non-linear.